package leetcode_61_80;

import java.util.ArrayList;
import java.util.List;

public class addBinary_67 {
    /**
     * 二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
     *
     * 2ms  30%  真拉跨，简单难度
     * @param a
     * @param b
     * @return
     */
    public String addBinary(String a, String b) {
        StringBuilder s=new StringBuilder();
        int carry=0;
        List<Integer> res=new ArrayList<>();  //防止首位进位
        for(int i=a.length()-1,t=b.length()-1;;t--,i--){
            int temp=a.charAt(i)-'0'+b.charAt(t)-'0'+carry;
            if(temp>1){
                carry=1;
                res.add(temp%2);
            }else{
                res.add(temp);
                carry=0;
            }
            if (i == 0) {
                for (int j =t-1; j >= 0; j--) {
                    if(carry>0){
                        int temp2=b.charAt(j)-'0'+carry;
                         res.add((temp2)% 2);
                         carry=temp2>1?1:0;
                    }else
                        res.add(b.charAt(j)-'0');
                }
                break;
            }
            if (t == 0) {
                for (int j =i-1; j >= 0; j--) {
                    if(carry>0){
                        int temp2=a.charAt(j)-'0'+carry;
                        res.add((temp2)% 2);
                        carry=temp2>1?1:0;
                    }else
                        res.add(a.charAt(j)-'0');
                }
                break;
            }

        }
        if(carry==1)
            res.add(1);
        for(int i=res.size()-1;i>=0;i--)
            s.append(res.get(i));
        return s.toString();
    }

    /**
     *整体思路是将两个字符串较短的用 0 补齐，使得两个字符串长度一致，
     * 然后从末尾进行遍历计算，得到最终结果。
     * 1ms
     * @param a
     * @param b
     * @return
     */
    public String addBinary2(String a, String b) {
        StringBuilder ans = new StringBuilder();
        int carry = 0;
        for(int i = a.length() - 1, j = b.length() - 1;i >= 0 || j >= 0; i--, j--) {
            int sum = carry;
            sum += i >= 0 ? a.charAt(i) - '0' : 0; //如果该位没有数字，就当作0计算
            sum += j >= 0 ? b.charAt(j) - '0' : 0;
            ans.append(sum % 2);
            carry = sum / 2;
        }
        ans.append(carry == 1 ? carry : "");
        return ans.reverse().toString();
    }
}
